import java.util.List;

public class MySingleList {
    static class ListNode {
        public int vale;
        public ListNode next;

        public ListNode(int vale) {
            this.vale = vale;
        }
    }

    public ListNode head;

    public void creat() {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        head = node1;
    }

    public void show() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.vale + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public void show(ListNode newhead) {
        ListNode cur = newhead;
        while (cur != null) {
            System.out.print(cur.vale + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public void addFirst(int data) {
        ListNode listNode = new ListNode(data);
        listNode.next = head;
        head = listNode;
    }

    public void addLast(int data) {
        ListNode listNode = new ListNode(data);
        if (head == null) {
            head = listNode;
            return;
        }
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = listNode;
    }

    public void check(int index) {

        if (index < 0 || index > size()) {
            throw new PosOutOfBoundsException("添加元素位置不合法：" + index);
        }
    }

    public void addAll(int index, int data) {
        int len = size();
        check(index);
        if (index == 0) {
            addFirst(data);
        } else if (index == len) {
            addLast(data);
        }
        ListNode listNode=new ListNode(data);
      ListNode pre=preFind(index);
        listNode.next=pre.next;
        pre.next=listNode;

    }

    public int size() {
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    public ListNode preFind(int index) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode cur = head;
        for (int i = 0; i < index - 1; i++) {
            cur = cur.next;
        }
        return cur;
    }
    //查找是否有关键字key在列表中
    public boolean contains(int key){
        ListNode cur=head;
        while (cur.next!=null){
            if (cur.vale==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    //删除第一次出现的关键字key
    public void removeFistKey(int key){
        if(head==null){
            return;
        }
        if (head.vale==key){
            head=head.next;
            return;
        }
        ListNode pre=prekey(key);
        if (pre==null){
            return;
        }
        pre.next=pre.next.next;

    }
    public void removeAllKey(int key){
        if (head==null){
    return;
        }
        ListNode cur=head.next;
        ListNode pre=head;
while (cur!=null){
    if(cur.vale==key){
        pre.next=cur.next;
        cur=cur.next;
    }else {
        pre=cur;
        cur=cur.next;
    }
    if (head.vale==key){
        head=head.next;
    }
}
    }
    public ListNode prekey(int key) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode cur = head;
        while (cur.next!=null){
            if (cur.next.vale==key){
                return cur;
            }
            cur=cur.next;
        }
return null;
    }
    public void clear(){
        head=null;
    }
    //递归求倒列表
    public ListNode reverseList(ListNode head){
        if (head==null||head.next==null){
            return head;
        }
        ListNode newhead=reverseList(head.next);
        head.next.next=head;
       head.next=null;
        return newhead;
    }
    //循环求
    public ListNode reverseList1(){
        if (head==null){
            return head;
        }
        ListNode cur=head.next;
        head.next=null;
        while (cur!=null){
            ListNode curn=cur.next;
            cur.next=head;
            head=cur;
            cur=curn;
        }
        return head;
    }
    //给你单链表的头结点 head ，请你找出并返回链表的中间结点。
    //
    //如果有两个中间结点，则返回第二个中间结点。
    public ListNode middleNode(ListNode head) {
        if(head==null||head.next==null)
            return head;
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){

            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }

    //回文链表


        public boolean chkPalindrome(ListNode A) {
            // write code here
              ListNode quikly=head;
              ListNode slow=head;
           while (quikly!=null||quikly.next!=null){
               quikly=quikly.next.next;
               slow=slow.next;
       }
           ListNode cur=slow;
           while (cur!=null){
           ListNode curn=cur.next;
           curn.next=cur;
           cur=cur.next;
          slow=cur;
           }
           while (head!=slow){
               if (head.vale!=slow.vale){
                   return false;
               }else {
                   head=head.next;
                   slow=slow.next;
               }
           }
return true;
        }
//求倒数第k个节点的值

    public int kthToLast(ListNode head, int k) {
        ListNode fast=head;
        ListNode slow=head;
        for(int i=0;i<k;i++){
            fast=fast.next;
        }
        while(fast!=null){
            slow=slow.next;
            fast=fast.next;
        }
        return slow.vale;
    }
    //链表分割
    public class Partition {
        public ListNode partition(ListNode pHead, int x) {
ListNode at=null;
ListNode aw=null;
ListNode bt=null;
ListNode bw=null;
ListNode cur=head;
while (cur!=null){
    if (cur.vale<x){
        if (at==null){
            at=cur;
            aw=cur;
        }else {
            aw.next=cur;
            aw=aw.next;
         }
    }else {
if (bt==null){
   bt=cur;
   bw=cur;
}else {
    bw.next=cur;
    bw= bt.next;
    }
}
        }
            if (at==null){
                return bt;
            }
            if (bw!=null){
                bw.next=null;
            }
            aw.next=bt;
            return aw;
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode nwehead=new ListNode(1);
        ListNode temp=nwehead;
        while(list1!=null&&list2!=null){
            if(list1.vale>list2.vale){
                temp.next=list2;
                temp=temp.next;
                list2=list2.next;
            }else{
                temp.next=list1;
                temp=temp.next;
                list1=list1.next;
            }
        }
        if(list1==null){
            temp.next=list2;
        }
        if(list2==null){
            temp.next=list1;
        }


        nwehead=nwehead.next;
        return nwehead;
    }

}
//是否有圈
public boolean hasCycle(ListNode head) {
        ListNode quik=head;
        ListNode slow=head;
        while(quik!=null&&quik.next!=null){

            quik=quik.next.next;
            slow=slow.next;
            if(quik==slow){
                return true;
            }
        }
        return false;
    }
    //找公共节点
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA=0;
        int lenB=0;
        ListNode pA=headA;
        ListNode pB=headB;
        while (pA!=null){
            lenA++;
            pA=pA.next;
        }
        pA=headA;
        while (pB!=null){
            lenB++;
            pB=pB.next;
        }
        pB=headB;
        int len=lenA-lenB;
        if (len<0){
            pA=headB;
            pB=headA;
            len=lenB-lenA;
        }
        while (len!=0){
            pA=pA.next;
            len--;
        }
        while (pA==pB){
            pA=pA.next;
            pB= pB.next;
        }
        if (pA==null){
            return null;
        }
        return pA;

    }
    //找环形链表节点
    public ListNode detectCycle(ListNode head) {
ListNode quick=head;
ListNode slow=head;
while (quick!=null&&quick.next!=null){
    quick=quick.next.next;
    slow=slow.next;
    if (quick==slow){
        slow=head;
        break;
    }
}
if (quick.next==null||quick==null){
    return null;
}
while (quick!=slow){
    quick=quick.next;
    slow=slow.next;
}
return quick;
    }
}


